package com.stable;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
/**
 * 
 * @author Bhattacharjee, Bhatia
 * COP 5537, Network optimization
 * Project Code: Stable Marriage Program
 * Implementation and comparision of the paper 
 * Local search for stable marriage problems with ties and incomplete lists
 * with old approaches
 */
public class LocalSearchAlgo {

	private static Random rand = new Random();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		boolean again = true;
		/*
		 * **************************************************************
		 *		Algorithm Starts here,
		 *	Implementation and comparision of the paper 
		 *Local search for stable marriage problems with ties and incomplete lists
		 * with old approaches
		 * 
		 **************************************************************** 	
		 */

		LSNodeClass M = null, M_best = null;
		int f_M = 0, f_best = 0;
		int step = 0;

		LocalSearchSM sm = new LocalSearchSM(10, 0.3, 0.3, true);

		int[] randomMarriage = new int[sm.getN()];
		int[] rmPrefMan = new int[sm.getN()];
		int[] rmPrefWoman = new int[sm.getN()];

		HashMap<Integer, Integer> blockingPairs;
		
		while(again){
		randomMarriage = sm.createRandomMarriage(sm.isMan());
		sm.printRandomMarriage(randomMarriage);
		rmPrefMan = sm.findPrefofRM(randomMarriage, true);// true for man
		sm.printPrefRM(rmPrefMan, true);
		rmPrefWoman = sm.findPrefofRM(randomMarriage, false);
		sm.printPrefRM(rmPrefWoman, false);

		int noOfSingles = sm.findSingleRM(randomMarriage);
		System.out.println("No. of singles in Random Marriage: " + noOfSingles);

		//sm.printBlockinPairs(blockingPairs);

		M = new LSNodeClass(randomMarriage, rmPrefMan, rmPrefWoman);

		M_best = new LSNodeClass(randomMarriage, rmPrefMan, rmPrefWoman);
		blockingPairs = sm.findBlockingPair(M_best.getRandomMarriage(),
				M_best.getManPref(), M_best.getWomanPref());
		sm.printBlockinPairs(blockingPairs);
		f_best = sm.findEvl_Fun_Value(blockingPairs, M_best.getRandomMarriage());
		

		while (step < 100) {//termination criteria for program step = 100
			if(step == 99){
				again = false;
			}
			blockingPairs = sm.findBlockingPair(M.getRandomMarriage(),
					M.getManPref(), M.getWomanPref());
			sm.printBlockinPairs(blockingPairs);
			f_M = sm.findEvl_Fun_Value(blockingPairs, M.getRandomMarriage());
			if (f_M == 0) {	//Terminate if evalution function is zero.
				again = false;
				break;
				
			}
			if (rand.nextDouble() < 0.05) {
				M = rm_R_BP(M, sm);
			} else {
				if (blockingPairs.size() == 0) {
					break; //Problem restart with the new random marriage if it lacking any blocking pair.
					
					
				} else {
					int[] new_M = getBestNeighbour(M, blockingPairs, sm); // return best neighbour.
					rmPrefMan = sm.findPrefofRM(new_M, true);
					rmPrefWoman = sm.findPrefofRM(new_M, false);
					M = null;
					M = new LSNodeClass(new_M, rmPrefMan, rmPrefWoman);

				}
			}
			blockingPairs = sm.findBlockingPair(M.getRandomMarriage(),
					M.getManPref(), M.getWomanPref());
			f_M = sm.findEvl_Fun_Value(blockingPairs, M.getRandomMarriage());

			
			
			HashMap<Integer, Integer> blockingPairs_best = sm.findBlockingPair(
					M_best.getRandomMarriage(), M_best.getManPref(),
					M_best.getWomanPref());
			
			
			if ((blockingPairs.size() == 0) && (f_M < f_best)) {
				f_best = f_M;
				M_best = null;
				M_best = new LSNodeClass(M.getRandomMarriage(), M.getManPref(),
						M.getWomanPref());
			}
			if ((blockingPairs.size() != 0) && (blockingPairs.size() < blockingPairs_best.size())&& (f_M < f_best)) {
				f_best = f_M;
				M_best = null;
				M_best = new LSNodeClass(M.getRandomMarriage(), M.getManPref(),
						M.getWomanPref());
			}
			
			
			if ((blockingPairs.size() != 0) && (blockingPairs_best.size() != 0) && (f_M < f_best)) {
				f_best = f_M;
				M_best = null;
				M_best = new LSNodeClass(M.getRandomMarriage(), M.getManPref(),
						M.getWomanPref());
			}
			step++;
			}
		
		sm.printRandomMarriage(M_best.getRandomMarriage()); //print the best marriage found
		System.out.println("f_best: " + f_best);	//print the evaluation function value of best marriage found
		System.out.println("No. of steps: "+ step); //print number of steps required to find the best marrriage.
		}

	}

	
/**
 * Return the Random neigbour of Random marriage
 * @param m
 * @param sm
 * @return
 */
	private static LSNodeClass rm_R_BP(LSNodeClass m, LocalSearchSM sm) {
		
		int[] n_rm2 = null;
		int[] mpref = sm.findPrefofRM(m.getRandomMarriage(), true);
		int[] wpref = sm.findPrefofRM(m.getRandomMarriage(), false);	
		HashMap<Integer, Integer> bp = sm.findBlockingPair(m.getRandomMarriage(), mpref, wpref);
		
		if(bp.size() != 0){
		List<Integer> menList = new ArrayList<Integer>();
		for (Integer int1 : bp.keySet()) {
			menList.add(int1);
		}
		Collections.shuffle(menList);
		if(sm.isMan()){
			n_rm2 = removeBlockingpair(m.getRandomMarriage(), menList.get(0), bp.get(menList.get(0)), true);	
		}
		else{
			n_rm2 = removeBlockingpair(m.getRandomMarriage(), bp.get(menList.get(0)),menList.get(0), false);
		}
		
		
		 mpref = sm.findPrefofRM(n_rm2, true);
		 wpref = sm.findPrefofRM(n_rm2, false);
		LSNodeClass n_rm = new LSNodeClass(n_rm2, mpref, wpref);
		return n_rm;
		}else{
			return m;
		}
		
	}

	/**
	 * 
	 * @param m
	 * @param blockingPairs
	 * @param sm
	 * @return best neighbour of random marriage 
	 */
	public static int[] getBestNeighbour(LSNodeClass m,	HashMap<Integer, Integer> blockingPairs, LocalSearchSM sm) {
			int[] n_rm1 =null, n_rm2 = null;
			int f_new1 = 0, f_new2 = 0;
			
			int count = 0;
			for (Integer sets :	blockingPairs.keySet() ) {
				if(sm.isMan()){
					n_rm2 = removeBlockingpair(m.getRandomMarriage(), sets, blockingPairs.get(sets), true);	
				}
				else{
					n_rm2 = removeBlockingpair(m.getRandomMarriage(), blockingPairs.get(sets),sets, false);
				}
				
				int[] mpref = sm.findPrefofRM(n_rm2, true);
				int[] wpref = sm.findPrefofRM(mpref, false);	
				HashMap<Integer, Integer> bp = sm.findBlockingPair(n_rm2, mpref, wpref);
				f_new2 = sm.findEvl_Fun_Value(bp, n_rm2);
				if(count == 0){
					n_rm1 = n_rm2;
					f_new1 = f_new2;
					count++;
				}
				else{
					if(f_new2 < f_new1){
						n_rm1 = n_rm2;
						f_new1 = f_new2;
					}
				}
				
				
				
			}
			
			
			return n_rm1;
		
		
		
	}
	
	/**
	 * 
	 * @param rm
	 * @param man
	 * @param woman
	 * @param m
	 * @return Neigbour Marriage after removing provided Blocking pair
	 */
	public static int[] removeBlockingpair(int[] rm, int man, int woman, boolean m){
		int[] rm_new = new int[rm.length];
		for (int i = 0; i < rm.length; i++) {
			int j = rm[i];
			rm_new[i] = j;
		}
		int fm1 = -1;
		int m1 = -1;
		
		if(m){
			
			for (int i = 0; i < rm_new.length; i++) {
				if(rm_new[i] == woman){
					m1 = i;
				}
			}
			if(m1 != -1){
				rm_new[m1] = -1;
			}
			rm_new[man] = woman;
			
			
		}else{
			for (int i = 0; i < rm_new.length; i++) {
				if(rm_new[i] == man){
					fm1 = i;
				}
			}
			if(fm1 != -1){
				rm_new[fm1] = -1;
			}
			rm_new[woman] = man;
			
		}
		
		
		return rm_new;
	}


	
	
	
}
